package algorithm.sort;

import java.util.Arrays;

/**
 * 插入排序
 *
 * @author hck
 */
public class InsertSort {
    public static void main(String[] args) {
        int[] array = {6, 8, 1, 9, 2, 5, 4, 3, 7};
        System.out.println("source array: " + Arrays.toString(array));
        sort(array);
        System.out.println("sorted array: " + Arrays.toString(array));
    }

    /**
     * 插入排序
     *
     * @param array
     */
    public static void sort(int[] array) {
        if (null == array || array.length == 0 || array.length == 1) {
            return;
        }
        int count = 0;
        //  默认第一个数为有序数组
        //  默认第二个数到最后一个为无序数组
        //  设定index 从1开始
        for (int i = 1; i < array.length; i++) {
            //  待插入的数
            int indexNum = array[i];
            //  标识待插入的位置
            int sortIndex = i - 1;
            //  从有序数组最后一位向前遍历,找到合适的位置
            while (sortIndex >= 0 && indexNum < array[sortIndex]) {
                //  同时将数组向后移
                array[sortIndex + 1] = array[sortIndex];
                sortIndex--;
                count++;
            }
            sortIndex++;
            if (sortIndex != i) {
                array[sortIndex] = indexNum;
            }
        }
        System.out.println("次数:" + count);
    }
}
